#include <bits/stdc++.h>

using namespace std;

// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的组合
// 答案 不能 包含重复的组合。返回的答案中，组合可以按 任意顺序 排列
// 注意其实要求返回的不是子集，因为子集一定是不包含相同元素的，要返回的其实是不重复的组合
// 比如输入：nums = [1,2,2]
// 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
// 测试链接 : https://leetcode.cn/problems/subsets-ii/

class Solution 
{
private:
    vector<vector<int>> ret;
    vector<int> path;

    void f(vector<int>& nums, vector<int>& path, int i, int size)
    {
        if(i == nums.size())
        {
            ret.emplace_back(vector<int>(path.begin(), path.begin() + size));
            return;
        }

        // 下一组的第一个数的位置
        int j = i + 1;
        while(j < nums.size() && nums[j] == nums[i]) ++j;
        // 当前数x，要0个
        f(nums, path, j, size);
        // 当前数x，要1个、要2个、要3个...都尝试
        for(; i < j; ++i)
        {
            path[size++] = nums[i];
            f(nums, path, j, size);
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        path.resize(nums.size());
        f(nums, path, 0, 0);
        return ret;
    }
};


class Solution 
{
private:
    vector<vector<int>> ret;
    vector<int> path;

    void dfs(const vector<int> nums, int startIndex)
    {
        ret.push_back(path); // [startIndex ...] 的元素都没要
        if(startIndex == nums.size())
            return;
        
        for(int i = startIndex; i < nums.size(); ++i)
        {
            if(i > startIndex && nums[i] == nums[i - 1]) // 去重
                continue;
            
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return ret;
    }
};